﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.dfs
{
    //37.解数独
    //编写一个程序，通过已填充的空格来解决数独问题。

    //一个数独的解法需遵循如下规则：

    //数字 1-9 在每一行只能出现一次。
    //数字 1-9 在每一列只能出现一次。
    //数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    //空白格用 '.' 表示。
    public class _37
    {
        public void SolveSudoku(char[][] board)
        {
            Boolean[,] rowUsed = new Boolean[9,10];
            Boolean[,] colUsed = new Boolean[9,10];
            Boolean[,,] boxUsed = new Boolean[3, 3, 10];
            for (int row = 0; row < board.Length; row++)//初始化
            {
                for (int col = 0; col < board[0].Length; col++)
                {
                    int num = board[row][col] - '0';
                    if (1<=num&&num<=9)
                    {
                        rowUsed[row,num] = true;//board行数据有num 这个数字
                        colUsed[col, num] = true;//board列数字有num 这个数字
                        boxUsed[row/3,col/3, num] = true;//3*3 格子里边有num 这个数字(board)
                    }
                }
            }
            dfs(board, rowUsed, colUsed, boxUsed, 0,0);
        }
        public bool dfs(char[][] board, Boolean[,] rowUsed, Boolean[,] colUsed, Boolean[,,] boxUsed, int row, int col)
        {
            if (col==board[0].Length)
            {
                col = 0;
                row++;
                if (row == board.Length)
                {
                    return true ;
                }
            }
            if (board[row][col] =='.')//当前的没有数字
            {
                for (int i = 1; i <= 9; i++)
                {
                    bool canUsed = !(rowUsed[row, i]|| colUsed[col, i]|| boxUsed[row / 3, col / 3, i]);
                    if (canUsed)//当前数字符合就插入
                    {
                        rowUsed[row, i] = true;
                        colUsed[col, i] = true;
                        boxUsed[row / 3, col / 3, i] = true;
                        board[row][col] = Convert.ToChar('0'+i);
                        if (dfs(board, rowUsed, colUsed, boxUsed, row, col + 1))
                        {
                            return true;//当前
                        }
                        board[row][col] = '.';
                        rowUsed[row, i] = false;
                        colUsed[col, i] = false;
                        boxUsed[row / 3, col / 3, i] = false;
                    }
                }
            }
            else
            {
                return dfs(board, rowUsed, colUsed, boxUsed, row, col + 1);
            }
            return false;
        }
    }
}
